// 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。
// 如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
// 你可以假设数组中无重复元素。

function searchInsert(nums: number[], target: number): number {
  let left: number = 0;
  let right: number = nums.length - 1;
  // 边界情况的极端情况：需要插在末尾->target极大
  if (nums[right] < target) return right + 1;
  //二分查找算法 ---> 截止终点：left = right
  while (left < right) {
    let mid: number = Math.floor((left + right) / 2);
    if (nums[mid] === target) {
      return mid;
    } else if (nums[mid] < target) {
      left = mid + 1; // 此时mid一定不是解
    } else {
      right = mid; // 此时无法判断mid不是解
    }
  }
  return right;
}

// 这道题目也是一道非常明显且经典的二分查找的算法题（有序数组+查找索引）
// 整体而言，这道二分查找的思路是在循环的过程中，不断排除不需要的解，
// 最后剩下的那个元素的位置就一定是插入元素的位置。
// 首先考虑一个边界情况：插入位置有可能插在数组的末尾（即搜索值极大），
// 此时需要单独判断，需要直接返回数组的长度；
// 接下来我们就可以进入二分搜索的主算法区间，插入的位置是大于等于 target 的第 1 个元素的位置
// 实例如：[1,3,5,6,7,11]中插入4，我们可以得出当mid小于target时得到的元素一定不是解
// 相反当mid>target时我们无法判断mid不是解，
// 基于这个思路做减治，我们就可以得到代码，当区间收窄到一个元素时即可得到答案。
